\documentclass{beamer}
\usetheme{Berkeley}
\usepackage{geometry}

\title{Extensibility, Safety and Performance in the SPIN Operating System}
\author{Dennis Castleberry \& Sudip Biswas}
\date{\today}

\begin{document}

\begin{frame} \maketitle
\end{frame}

\begin{frame} 
\frametitle{Goals}
 \begin{itemize}
  \item As the title indicates, the key aims of the SPIN operating system include:
  \begin{itemize}
   \item \textbf{extensibility}: to adapt to application needs
   \item \textbf{safety}: in a way that provides fine-grained access control
   \item \textbf{performance}: with as little overhead as possible
  \end{itemize}
  \item Extensions in SPIN allow an application to specialize the OS for
        optimal performance and functionality
 \end{itemize}
\end{frame}

\begin{frame}
\frametitle{Motivation}
 \begin{itemize}
  \item SPIN is motivated by the poor match between kernel implementation and application needs
  \item Examples:
  \begin{itemize}
   \item disk buffering and paging algorithms in a general-purpose OS may be inappropriate for a database server 
   \item network protocols for a general-purpose OS may be inappropriate for parallel computing
  \end{itemize}
 \end{itemize}
\end{frame}

\begin{frame}
\frametitle{Techniques}
 \begin{itemize}
  \item Four techniques are used to achieve these ends:
  \begin{itemize}
   \item \textbf{co-location}: extensions are linked into the kernel virtual address space
   \item \textbf{enforced modularity}: extensions are written in Modula-3, modular programming langauge for which the compiler enforces interface boundaries between modules at compile-time
   \item \textbf{logical protection domains}: kernel namespaces that contain code and exported interfaces
   \item \textbf{dynamic call binding}: extensions execute in response to system events, such as a page fault or scheduling of a thread
  \end{itemize}
 \end{itemize}
\end{frame}

\begin{frame}
\frametitle{Features of Modula-3}
 \begin{itemize}
  \item SPIN and extensions are written in Modula-3, a general-purpose programming language developed in the early 90s
  \item Most important Modula-3 features:
  \begin{itemize}
   \item \textbf{interfaces}: declares visible parts of an implementation \textbf{module}, which defines items listed in the interface
   \item \textbf{type safety}: prevents code from accessing memory arbitrarily; pointer can only refer to objects of its type, and array indexing ops must be checked for bounds violation
   \item \textbf{automatic storage management}: prevents memory used by a live pointer's referent from being returned to the heap and reused for an object of a different type
  \end{itemize}
  % Give example of module
 \end{itemize}
\end{frame}

\begin{frame}
\frametitle{Capabilities}
 \begin{itemize}
  \item All kernel resources in SPIN are referenced by capabilities
  \item A \textbf{capability} is an unforgeable reference to a resource 
  \item What's a resource? A system object, interface, or collection of interfaces\ldots e.g. physical page, physical page allocation interface, entire virtual memory system
  \item SPIN implements capabilities with pointers; the pointer references a block of memory whose type is declared within an interface
  \item At compile time, the compiler prevents a pointer from being forged or dereferenced in a manner inconsistent with its type
 \end{itemize}
\end{frame}

\begin{frame}
\frametitle{Protection Domains}
 \begin{itemize}
  \item SPIN uses \text{protection domains} to define the set of accessible names available to an execution context
  \item Namespace management occurs at the language level; SPIN provides facilities for creating, coordinating, linking program-level namespaces in the context of protection domains
  % Show the domain module
 \end{itemize}
\end{frame}

\begin{frame}
\frametitle{Extension Model}
 \begin{itemize}
  \item SPIN's extension model provides a controlled communication facility between extensions and the base system
  \item This allows extensions to passively monitor system activity and provide up-to-date performance information to applications
  \item Extensions in SPIN are defined in terms of events and handlers
 \end{itemize}
\end{frame}

\begin{frame}
\frametitle{Extension Model}
 \begin{itemize}
  \item An \textbf{event} is a message that announces a change in the state of the system or a request for service; it is a procedure exported from an interface
  \item An event \textbf{handler} is a procedure that receives the message; it has the same type as the event procedure
  \item An extension installed a handler on an event by explicitly registering the handler with the event through a central \textbf{dispatcher} that routes events with handlers
  \item The right to call a procedure is equivalent to the right to raise an event named by the procedure
 \end{itemize}
\end{frame}

\begin{frame}
\frametitle{Extension Model}
 \begin{itemize}
  \item Single handler for an event is a direct procedure call; multiple handler for an event involves dynamic code generation
  \item The primary implementation module (a handler) decides whether to admit or reject the installation of a new handler; it also has control over the execution (synchronous/asynchronous) of a handler
 \end{itemize}
\end{frame}

\begin{frame}
 \includegraphics[width=\textwidth]{s1.png}
\end{frame}

\begin{frame}
 \includegraphics[width=\textwidth]{s2.png}
\end{frame}

\begin{frame}
\frametitle{Thread Management}
 \begin{itemize}
  \item Tradeoff between scheduler activation and user-level thread management
  \item Applications provide their own thread package and scheduler which executes within kernel
  \item A scheduler multiplexes the underlying processing resources among competing contexts called strands using round robin, preemptive, priority policy
  \item Thread package and the scheduler implement the control flow mechanisms for user space contexts
  \item Scheduler can communicate with the thread package managing the strand using \emph{Checkpoint} and \emph{Resume} events
 \end{itemize}
\end{frame}

\begin{frame}
 \begin{center}
  \includegraphics[width=.8\textwidth]{s3.png}
 \end{center}
\end{frame}

\begin{frame}
\frametitle{Extensible Memory Management}
 \begin{itemize}
  \item Three components: physical storage, naming and translation
  \begin{enumerate}
   \item Physical address service manages allocation of physical pages
   \item Virtual address service manages capabilities for virtual addresses
   \item Translation service manages relationship between physical and virtual addresses
  \end{enumerate}
  \item Extensions use the events raised by these three modules to create their own memory management schemes
 \end{itemize}
\end{frame}

\begin{frame}
 \includegraphics[width=\textwidth]{s4.png}
\end{frame}

\begin{frame}
\frametitle{Protection Domains}
\begin{itemize}
 \item Defines a set of accessible names available to an execution context
 \item Virtual address space and language level naming
 \item Domains can be intersecting or disjoint
 \begin{enumerate}
  \item Create: creates domain from safe object fine with one or more exported interface
  \item Resolve: resolves any unresolved symbol in the target domain
  \item Combine: creates a new aggregate domain from two existing domains
 \end{enumerate}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Performance Analysis: Perspectives}
 \begin{itemize}
  \item Performance analysis done from four perspectives: 
  \begin{itemize}
   \item system size: lines of code, size of kernel 
   \item microbenchmarks: measurements of overhead on protected comm., thread management and virtual memory
   \item networking: measures of latency for network comm.
   \item end-to-end performance: cases of applications that use extensions
  \end{itemize}
  \item Measurements are compared with those for the: 
   \begin{itemize}
    \item DEC OSF/1 monolithic operating system 
    \item Mach 3.0 microkernel
   \end{itemize}
 \end{itemize}
\end{frame}

\begin{frame}
\frametitle{Performance Analysis: System Size}
 Size of the SPIN kernel: \\
 \vspace{12pt}
 \begin{tabular}{lll}
 lines & text size & data size \\
 65652 & 810550    & 447274 \\
 \end{tabular} \\
 \vspace{16pt}
 March 1995 release of Linux 1.2.0: \\
 \vspace{12pt}
 \begin{tabular}{lll}
 lines & text size & data size \\
 310950 & & \\
 \end{tabular}
\end{frame}

\begin{frame}
\frametitle{Performance Analysis: Microbenchmarks}
 Overhead for calls (in microseconds): \\
 \vspace{12pt}
 \begin{tabular}{lrrr}
 operation & DEC OSF/1 & Mach & SPIN \\
 protected in-kernel call & n/a & n/a & .13 \\
 system call & 5 & 7 & 4 \\
 cross-address space call & 845 & 104 & 89 \\
 \end{tabular}
\end{frame}

\begin{frame}
 Thread management overhead for kernel: \\
 \vspace{10pt}
 \begin{tabular}{lrrr}
 operation & DEC OSF/1 & Mach & SPIN \\
 fork-join & 198       & 101  & 22   \\
 ping-pong & 21        & 71   & 17   \\
 \end{tabular} \\
 \vspace{16pt}
 Thread management overhead for user: \\
 \vspace{10pt}
 \begin{tabular}{lrrr}
 operation & DEC OSF/1 & Mach & SPIN \\
 fork-join & 1230      & 338  & 262/111 \\
 ping-pong & 264       & 115  & 159/85  \\
 \end{tabular} \\
 \vspace{12pt}
 \emph{Fork-Join} measures the time to create, schedule and terminate a new thread, synchronizing the termination with another thread;
 \emph{Ping-Pong} reflects synchronization overhead, and measures the time for a pair of threads to synchronize with one another
\end{frame}

% Add description
\begin{frame}
\frametitle{Performance Analysis: Microbenchmarks}
 Overhead on memory management operations: \\
 \vspace{12pt}
 \begin{tabular}{lrrr}
 operation & DEC OSF/1 & Mach & SPIN \\
 dirty & n/a & n/a & 2 \\
 fault & 329 & 415 & 29 \\
 trap & 260 & 185 & 7 \\
 prot1 & 45 & 106 & 16 \\
 prot100 & 1041 & 1792 & 213 \\
 unprot100 & 1016 & 302 & 214 \\
 appel1 & 382 & 819 & 39 \\
 appel2 & 351 & 608 & 29 
 \end{tabular}
\end{frame}

\begin{frame}
\frametitle{Performance Analysis: Networking}
 Network protocol latency (microseconds) and bandwidth (Mb/sec): \\
 \vspace{12pt}
 \begin{tabular}{lrr}
           & DEC OSF/1 & SPIN \\
 latency   & 789 & 631 \\
 bandwidth & 8.9 & 8.9 \\
 \end{tabular} \\
 \vspace{12pt}
 Latency is measured with 16-byte packets, bandwidth with 1500-byte packets
\end{frame}

\begin{frame}
\frametitle{Performance Analysis: Networking}
 Network protocol latency (microseconds) for TCP/UDP: \\
 \vspace{12pt}
 \begin{tabular}{lrr}
 protocol & DEC OSF/1 & SPIN \\
 TCP & 2080 & 1420 \\
 UDP & 1607 & 1344
 \end{tabular} \\
 \vspace{12pt}
 This is round-trip latency to route 16-byte packets through a protocol forwarder
\end{frame}

\begin{frame}
\frametitle{Performance Analysis: End-to-End}
 \begin{itemize}
  \item A networked video system consisting of a server and a client viewer
        was run on SPIN as well as DEC OSF/1.
  \item CPU utilization as a function of the number of connected clients
        was measured for each.
  \item DEC OSF/1 utilizes an additional 2.8\% for each client, whereas SPIN 
        utilizes only 1.7\%.
 \end{itemize}
\end{frame}

\begin{frame}
\frametitle{SPIN: Afterthoughts}
 \begin{itemize}
  \item One clear disadvantage of SPIN is that extensions have 
        to be written per-application.
  \item Also, it is not clear what motivates the choice of DEC OSF/1 and
        Mach as comparators for SPIN for the performance analysis.
 \end{itemize}
\end{frame}

% Add cases
\end{document}
